package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 题目-03. 重复的彩灯树
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/26 10:19
 */
public class LightDistribution {

    public static void main(String[] args) {
        LightDistribution test = new LightDistribution();
        TreeNode instance20 = TreeNode.getInstance20();
        List<TreeNode> treeNodes = test.lightDistribution(instance20);
        System.out.println(treeNodes);

        for (Map.Entry<String, List<TreeNode>> entry : test.map.entrySet()) {
            if (entry.getValue().size() > 1) {
                System.out.println(entry.getKey());
                System.out.println(entry.getValue());
            }
        }
    }

    private Map<String, List<TreeNode>> map = new HashMap<>();

    public List<TreeNode> lightDistribution(TreeNode root) {
        find(root);
        List<TreeNode> list = new ArrayList<>();
        for (Map.Entry<String, List<TreeNode>> entry : map.entrySet()) {
            if (entry.getValue().size() > 1) {
                list.add(entry.getValue().get(0));
            }
        }
        return list;
    }

    private StringBuilder find(TreeNode node) {
        if (node == null) {
            return new StringBuilder("N");
        }
        StringBuilder sb = find(node.left);
        sb.append("l");
        sb.append(find(node.right));
        sb.append("r");
        sb.append(node.val);
        map.computeIfAbsent(sb.toString(), v -> new ArrayList<>()).add(node);
        return sb;
    }

}
